import re

def simple_m1(w):
    state = 1
    for c in w:
        if state == 1:
            if c == 'a':
                state = 2
        if state == 2:
            if c == 'a' or c == 'b':
                state = 3
        if state == 3:
            if c == 'b':
                state = 1
            elif c == 'a':
                state = 2
    return state == 2

def dfa(transitions, final, w):
    q = 0
    for c in w:
        q = transitions[q][c]
    return q in final

transitions1 = [{} for i in range(3)]
transitions1[0]['a'] = 1
transitions1[0]['b'] = 0
transitions1[1]['a'] = 2
transitions1[1]['b'] = 2
transitions1[2]['a'] = 1
transitions1[2]['b'] = 0

def make_dfa(transitions, final):
    return lambda w: dfa(transitions, final, w)

def print_match(pattern, s):
    print s,
    if re.search(pattern, s):
        print "\tmatches %s" % (pattern,)
    else:
        print "\tdoes not match %s" % (pattern,)
